class Solution {  // 一维bool版本
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i];
        }
        if(sum % 2 == 0) // 01背包凑刚好能等于sum / 2的子集
            sum /= 2;
        else
            return false;
        
        vector<bool> dp(sum + 1, false);
        dp[0] = true;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = sum; j >= nums[i - 1]; --j)
            {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
        return dp[sum];
    }
};

/*class Solution {  // 二维bool版本
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i];
        }
        if(sum % 2 == 0) // 01背包凑刚好能等于sum/2的子集
            sum /= 2;
        else
            return false;
        
        vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false)); // dp[i][j]表示i为结尾，总和为j的数(是否可以到达)
        for(int i = 0; i <= n; ++i)
        {
            dp[i][0] = true;
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= sum; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1])
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
        return dp[n][sum];
    }
};*/
/*class Solution { // 二维int版本
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i];
        }
        if(sum % 2 == 0) // 01背包凑刚好能等于sum/2的子集
            sum /= 2;
        else
            return false;
        
        vector<vector<int>> dp(n + 1, vector<int>(sum + 1)); // dp[i][j]表示i为结尾，总和为j的数
        for(int j = 1; j <= sum; ++j)
        {
            dp[0][j] = -1;
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= sum; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] != -1)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
            }
        }
        return dp[n][sum] == -1 ? false : true;
    }
};*/